A new method for constructing minimum-redundancy binary prefix codes isdescribed. Our method does not explicitly build a Huffman tree; instead it usesa property of optimal prefix codes to compute the codeword lengthscorresponding to the input weights. Let $n$ be the number of weights and $k$ bethe number of distinct codeword lengths as produced by the algorithm for theoptimum codes. The running time of our algorithm is $O(k \cdot n)$. Followingour previous work in \cite{be}, no algorithm can possibly construct optimalprefix codes in $o(k \cdot n)$ time. When the given weights are presorted ouralgorithm performs $O(9^k \cdot \log^{2k}{n})$ comparisons.
展开▼
机译：描述了一种构造最小冗余二进制前缀码的新方法。我们的方法没有显式构建霍夫曼树。相反，它使用最佳前缀代码的属性来计算与输入权重相对应的代码字长度。令$ n $为权重数，$ k $为最佳代码算法产生的不同码字长度的数。我们算法的运行时间为$ O（k \ cdot n）$。按照先前在\ cite {be}中的工作，没有算法可以在$ o（k \ cdot n）$时间内构造最优前缀代码。当给定的权重被预先排序后，我们的算法将执行$ O（9 ^ k \ cdot \ log ^ {2k} {n}）$比较。
展开▼
